/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/perfect-squares
   @Language: C++
   @Datetime: 19-04-25 12:41
   */

class Solution {
public:
	/**
	 * @param n: a positive integer
	 * @return: An integer
	 */
	int numSquares(int n) {
		// write your code here
		vector<int> dp(n+1,0);
		for(int i=1; i<=n; ++i){
			int count=INT_MAX;
			for(int j=1; j<=sqrt(i); ++j)
				count=min(count,dp[i-j*j]);
			dp[i]=count+1;
		}
		return dp[n];
	}
};
